package com.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * N 叉树的后序遍历
 *
 * @author wangruiyang <wangruiyang@kuaishou.com>
 * Created on 2024-02-19
 */
public class No590 {

    class Node {
        @SuppressWarnings("checkstyle:VisibilityModifier")
        public int val;
        @SuppressWarnings("checkstyle:VisibilityModifier")
        public List<Node> children;

        public Node() {
        }

        @SuppressWarnings("checkstyle:ParameterName")
        public Node(int _val) {
            val = _val;
        }

        @SuppressWarnings("checkstyle:ParameterName")
        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    /**
     * 递归解法
     * @param root
     * @return
     */
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        for (Node child : root.children) {
            List<Integer> postorder = postorder(child);
            list.addAll(postorder);
        }
        list.add(root.val);
        return list;
    }

    /**
     * 利用栈非递归
     * @param root
     * @return
     */
    public List<Integer> postorder2(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<Node> temp = new ArrayDeque<>();
        Set<Node> visited = new HashSet<>();
        temp.push(root);
        while (!temp.isEmpty()) {
            Node node = temp.peek();
            if (visited.contains(node)) {
                list.add(node.val);
                temp.pop();
                continue;
            }
            for (int i = node.children.size() - 1; i >= 0; i--) {
                temp.push(node.children.get(i));
            }
            visited.add(node);
        }
        return list;
    }
}
